package com.cn.codebrush.数组;

/**
 * @Author Boolean
 * @Date 2022/6/16 12:06
 * @Version 1.0
 */
public class No121买卖股票的最佳时机 {


    /**
     * 动态规划
     * @param prices
     * @return
     */
    public int maxProfit3(int[] prices) {
        int n = prices.length;
        int minPri = prices[0];
        int val = 0;

        for(int i=1;i<n;i++){
            val = Math.max(val,(prices[i]-minPri));
            minPri = Math.min(minPri,prices[i]);
        }


        return val;
    }

    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int minPri = prices[0];
        int[] dp = new int[n];
        dp[0] = 0;

        for(int i=1;i<n;i++){
            dp[i] = Math.max(dp[i-1],(prices[i]-minPri));
            minPri = Math.min(minPri,prices[i]);
        }
        int res = 0;
        for(int i=0;i<dp.length;i++){
            res = Math.max(res,dp[i]);
        }

        return res;
    }

    /**
     * 203 / 211 个通过测试用例
     * 超出时间限制
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int res = 0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                res = res>(prices[j]-prices[i])?res:(prices[j]-prices[i]);
            }
        }

        return res;
    }
}
